#ifndef TRIANGLE_H
#define TRIANGLE_H

#include <cmath>

#include "point.h"
#include "segment.h"

class triangle
{
    public:
        class const_iterator
        {
            public:
                typedef const_iterator self_type;
                typedef std::pair<int, int> value_type;  
                typedef std::forward_iterator_tag iterator_category;

                const_iterator(const triangle& t, bool end = false) : t(t)
                {
                    if (end)
                    {
                        x = t.p3.x + 1;
                        y = 0;
                        y_end = 0;
                    }
                    else
                    {
                        x = std::floor(t.p1.x);
                        update_range();
                    }
                }

                self_type operator++()
                {
                    if (y < y_end)
                    {
                        y++;
                    }
                    else
                    {
                        if (x <= t.p3.x)
                            x++;

                        if (x <= t.p3.x)
                        {
                            update_range();
                        }
                        else
                        {
                            y = 0;
                            y_end = 0;
                        }
                    }

                    return *this;
                }

                self_type operator++(int t)
                {
                    self_type tmp = *this;

                    operator++();

                    return tmp;
                }

                value_type operator*()
                {
                    return std::make_pair(x, y);
                }

                bool operator==(const self_type& other) const
                {
                    return (t == other.t) && (x == other.x) && (y == other.y);
                }

                bool operator!=(const self_type& other) const
                {
                    return !(*this == other);
                }

            private:
                std::pair<int, int> get_range(segment a, segment b, int x) const
                {
                    double x1 = std::max(std::max(a.a.x, b.a.x), (double)x);
                    double x2 = std::min(std::min(a.b.x, b.b.x), (double)(x + 1));

                    double a1 = a.get_y(x1);
                    double a2 = a.get_y(x2);

                    double b1 = b.get_y(x1);
                    double b2 = b.get_y(x2);

                    double y_min = std::min(std::min(a1, a2), std::min(b1, b2));
                    double y_max = std::max(std::max(a1, a2), std::max(b1, b2));

                    if (((a1 >= b1 && a2 >= b2 && y_max == a2 && y_max != a1) || (b1 >= a1 && b2 >= a2 && y_max == b2 && y_max != b1)) && y_max == std::floor(y_max))
                        y_max -= 0.5;

                    return std::make_pair(std::floor(y_min), std::floor(y_max));
                }

                void update_range()
                {
                    if (x <= t.p2.x)
                    {
                        if (t.p1.x == t.p2.x)
                        {
                            y = std::floor(std::min(t.p1.y, t.p2.y));
                            y_end = std::floor(std::max(t.p1.y, t.p2.y));
                        }
                        else
                        {
                            std::pair<int, int> range = get_range(segment(t.p1, t.p2), segment(t.p1, t.p3), x);

                            y = range.first;
                            y_end = range.second;
                        }

                        if (x + 1 > t.p2.x)
                        {
                            if (t.p2.x == t.p3.x)
                            {
                                y = std::min(y, (int)std::floor(std::min(t.p2.y, t.p3.y)));
                                y_end = std::max(y_end, (int)std::floor(std::max(t.p2.y, t.p3.y)));
                            }
                            else
                            {
                                std::pair<int, int> range = get_range(segment(t.p2, t.p3), segment(t.p1, t.p3), x);

                                y = std::min(y, range.first);
                                y_end = std::max(y_end, range.second);
                            }
                        }
                    }
                    else
                    {
                        if (t.p2.x == t.p3.x)
                        {
                            y = std::floor(std::min(t.p2.y, t.p3.y));
                            y_end = std::floor(std::max(t.p2.y, t.p3.y));
                        }
                        else
                        {
                            std::pair<int, int> range = get_range(segment(t.p2, t.p3), segment(t.p1, t.p3), x);

                            y = range.first;
                            y_end = range.second;
                        }
                    }
                }

                const triangle& t;

                int x, y, y_end;
        };

        triangle(point a, point b, point c)
        {
            p1 = std::min(std::min(a, b, point_comparator()), c, point_comparator());
            p3 = std::max(std::max(a, b, point_comparator()), c, point_comparator());
            
            if (a != p1 && a != p3)
                p2 = a;
            else if (b != p1 && b != p3)
                p2 = b;
            else
                p2 = c;
        }

        const_iterator begin() const
        {
            return const_iterator(*this);
        }

        const_iterator end() const
        {
            return const_iterator(*this, true);
        }

        bool operator==(const triangle& other) const
        {
            return (p1 == other.p1) && (p2 == other.p2) && (p3 == other.p3);
        }

        point p1, p2, p3;
};

#endif
